package developer.算法.二叉树.将有序数组转换为二叉树;

/**
 * @author zhangyongkang
 * @time 2025/3/24 20:36
 * @description 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。
 * <p>
 * 输入：nums = [-10,-3,0,5,9]
 * 输出：[0,-3,9,-10,null,5]
 * 解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
 */
public class JiangYouXuShuZuZhuanHuanWeiErChaShu {

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode() {}
     * TreeNode(int val) { this.val = val; }
     * TreeNode(int val, TreeNode left, TreeNode right) {
     * this.val = val;
     * this.left = left;
     * this.right = right;
     * }
     * }
     */
    public static void main(String[] args) {
        Solution solution = new Solution();
        TreeNode node = solution.sortedArrayToBST(new int[]{-10, -3, 0, 5, 9});
        System.out.println(node);
    }


    static class Solution4 {

        public TreeNode sortedArrayToBST(int[] nums) {
            return handler(nums, 0, nums.length - 1);
        }

        public TreeNode handler(int[] nums, int start, int end) {
            if (start > end) {
                return null;
            }
            int midIdx = start + (end - start) / 2;
            TreeNode node = new TreeNode(nums[midIdx]);
            TreeNode left = handler(nums, start, midIdx - 1);
            TreeNode right = handler(nums, midIdx + 1, end);
            node.left = left;
            node.right = right;
            return node;
        }
    }

    static class Solution {
        public TreeNode sortedArrayToBST(int[] nums) {
            return handler(nums, 0, nums.length - 1);
        }

        public TreeNode handler(int[] nums, int start, int end) {
            if (start > end) return null;
            int mid = (start + end) / 2;
            TreeNode node = new TreeNode(nums[mid]);
            node.left = handler(nums, start, mid - 1);
            node.right = handler(nums, mid + 1, end);
            return node;
        }
    }

    class SolutionOfficial {
        /**
         * 作者：力扣官方题解
         * 链接：https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/solutions/312607/jiang-you-xu-shu-zu-zhuan-huan-wei-er-cha-sou-s-33/
         * 来源：力扣（LeetCode）
         * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
         *
         * @param nums
         * @return
         */

        public TreeNode sortedArrayToBST(int[] nums) {
            return helper(nums, 0, nums.length - 1);
        }

        public TreeNode helper(int[] nums, int left, int right) {
            if (left > right) {
                return null;
            }

            // 总是选择中间位置左边的数字作为根节点
            int mid = (left + right) / 2;

            TreeNode root = new TreeNode(nums[mid]);
            root.left = helper(nums, left, mid - 1);
            root.right = helper(nums, mid + 1, right);
            return root;
        }
    }


    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
